package com.lili.math;

import java.util.Arrays;

/**
 * @Auther: 李 力
 * @Date: 2024/8/3
 * @Description: 灯泡开关
 * @version: 1.0
 */
public class LeetCode319 {

    /*
     *   1    2     3       4     5    6
     *   Y    Y     Y       Y     Y    Y
     *   Y    N     Y       N     Y    N
     *   Y    N     N       Y     Y    Y
     *   0    1     2       3     4    5
     *
     *  时间复杂度: O(n^2)
     *  空间复杂度: O(1)
     *
     */
    public static int bulbSwitch(int n) {
        boolean[] arr = new boolean[n];
        Arrays.fill(arr, true);
        for (int i = 2; i <= n; i++) {
            for (int index = i; index <= n; index = index + i) {
                int r = index - 1;
                arr[r] = !arr[r];
            }
        }
        int count = 0;
        for (boolean b : arr) {
            if (b) {
                count++;
            }
        }
        return count;
    }

    //优化如下:
    public static int bulbSwitch2(int n) {
        return (int) Math.sqrt(n + 0.5);
    }
}